package done.normal_101_200;

import com.study.common.TreeNode;
import org.junit.Test;

import static com.study.util.LogUtil.info;

/**
 * 173. Binary Search Tree Iterator 二叉搜索树迭代器
 * <p>
 * 实现一个二叉搜索树迭代器。你将使用二叉搜索树的根节点初始化迭代器。
 * 调用 next() 将返回二叉搜索树中的下一个最小的数。
 * <p>
 * 示例：
 * 7
 * /   \
 * 3    15
 * /  \
 * 9   20
 * <p>
 * 2019-05-10 20:56
 **/
@SuppressWarnings("all")
public class BinarySearchTreeIterator {

    class BSTIterator {

        public BSTIterator(TreeNode root) {
            //TODO
        }

        public int next() {
            //TODO
            return -1;
        }

        public boolean hasNext() {
            //TODO
            return false;
        }
    }

    @Test
    public void test() {
        new BSTIterator(
                new TreeNode(7,
                        3, new TreeNode(15,
                        9, 20))) {{
            info(next());    // 返回 3
            info(next());    // 返回 7
            info(hasNext()); // 返回 true
            info(next());    // 返回 9
            info(hasNext()); // 返回 true
            info(next());    // 返回 15
            info(hasNext()); // 返回 true
            info(next());    // 返回 20
            info(hasNext()); // 返回 false
        }};
    }
}







































/*
class BSTIterator {

    Queue<TreeNode> queue = new LinkedList();

    //中序遍历 将节点存储到队列中
    public void fun(TreeNode root) {
        if (root == null)
            return ;
        fun(root.left);
        queue.offer(root);
        fun(root.right);
    }

    public BSTIterator(TreeNode root) {
        fun(root);
    }

    public int next() {
        return queue.poll().val;
    }

    public boolean hasNext() {
        if (!queue.isEmpty())
            return true;
        return false;
    }
}
*/